#
# @lc app=leetcode.cn id=2824 lang=python3
#
# [2824] 统计和小于目标的下标对数目
#


"""
题目要求返回满足条件的下标对的数目，而不是下标本身，所以数组内元素的顺序不影响结果
对数组进行排序以使用双指针
当 nums[left] + nums[right] < target 时，满足条件的下标对个数为 right-left 
（本质上是 nums[left] 和 nums[left] ... nums[right] 配对，共 right-left 对）
"""
# @lc code=start
class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0

        left, right = 0, len(nums) - 1
        while left < right:
            if nums[left] + nums[right] >= target:
                right -= 1
            else:
                res += right - left
                left += 1

        return res
# @lc code=end

